The present invention relates to techniques for mapping a circuit design to a programmable integrated circuit, and more particularly, to efficient technology mapping techniques for programmable integrated circuits.
Programmable integrated circuits can be programmed to implement many types of circuit designs. Examples of programmable integrated circuits include programmable logic devices (PLDs), complex programmable logic devices (CPLDs), field programmable gate arrays (FPGAs), programmable logic arrays (PLAs), and configurable logic arrays (CLAs).
Programmable integrated circuits include numerous programmable logic blocks. Each programmable logic block can be individually configured to implement combinatorial or sequential logic operations.
Altera's MAX family of PLDs are examples of programmable logic devices. Altera MAX devices include numerous programmable logic blocks called macrocells. Each macrocell has a logic array that can be configured to implement various combinatorial functions. Each macrocell also has a flip-flop that can implement sequential logic functions. Arrays of macrocells are grouped together into logic array blocks (LABs) on a MAX device.
A circuit design created by a user can be mapped onto a programmable integrated during a three step process. This process involves synthesis and technology mapping, placement, and routing. During synthesis and technology mapping, logic gates in the user design are converted into programmable logic blocks such as macrocells on a MAX device.
Specifically, synthesis is a process that generates an optimized, technology-independent, gate-level network from a user design. Technology mapping is a process that takes the gate-level network generated during synthesis and converts it to a network of programmable logic blocks. A technology mapping process for a MAX device converts a gate-level network into a network of macrocells.
A typical technology mapping process for a CPLD consists of two phases, a mapping phase and a macrocell-building phase. The mapping phase determines how the gate-level network should be converted to a macrocell network. The macrocell-building phase creates the macrocell network based on information provided by the mapping phase. Some tool also provide a third phase to optimize the macrocell network.
During the mapping phase, the mapper tool processes all the logic cones in the gate-level network of the user design. For each logic cone, the mapper tool maps nodes in the gate-level network in a topological order starting from the input boundary nodes. The topological ordering guarantees that every node is processed after all of its predecessors have been processed.
The mapper tool maps the logic cones by looking for output boundary nodes (i.e. registers or I/O pins). Starting from an output boundary node, the tool traverses backwards to the predecessor nodes in a depth-first-search manner, until reaching the input boundaries before mapping the nodes in a topological order.
Altera's Quartus II MAX Technology Mapper uses a multiple-merging-group algorithm during the mapping phase to provide information for the subsequent macrocell-building phase. It processes the nodes in a topological order starting from the input boundary nodes. Each non-boundary node tries to merge with different groups of predecessor nodes to form a macrocell. If all the merging groups fail to form a feasible macrocell, the node itself is formed as a new macrocell.
Each different merging group generates different depth and area of a macrocell network for the logic cone. Hence, the Technology Mapper selects the best merging group for the node-under-mapping by using a cost metric. The cost metric consists of depth and area information of macrocell network for the logic cone. Depth cost has priority over area cost to reduce the delay of the macrocell network.
The merging groups that the Quartus II Max Technology Mapper uses include (a) merging with all predecessor nodes, (b) merging with nodes until input boundaries or SOFT buffer boundaries, (c) merging with immediate fanin nodes, and (d) merging with nodes included in the best merging group of immediate fanin nodes.
In a multiple-merging-group algorithm such as Altera's Quartus II Max Technology Mapper, every node chooses among different merging groups to form a macrocell. The major weakness of this algorithm is that it cannot create a minimal depth macrocell network, though it may reduce area utilization.
Another type of prior art technology mapping tool is called a labeling algorithm. A labeling algorithm is used during the mapping phase of technology mapping to provide information for the subsequent macrocell-building phase. Its primary goal is to minimize the depth of a logic cone by annotating labels on the nodes during the mapping process.
In a labeling algorithm, every node has only one merging group, i.e. a node merges with predecessor nodes that have the maximum label. The major weakness for a labeling algorithm is that it does not consider other merging groups that may help in further reducing depth and area utilization of the macrocell network.
Therefore, it would be desirable to provide a more robust technology mapping process that optimizes signal delays and reduces area utilization in a synthesized user design for a programmable integrated circuit.